Computer networks generally include a plurality of interconnected computer systems. Some computer networks utilize a local computer for communicating data to one or more remote computers that are connected to the local computer through the network. From the remote computer, users may control or view activity on a local computer over the network utilizing a hardware interface device connected to the local computer. For instance, utilizing the interface device, a user may view screens of video data on the remote computer that were generated by the local computer. Each screen of video data may comprise thousands or millions of pixels, with each pixel representing a single point in a graphic image. Each point or pixel in a graphic image is represented by a predetermined number of bits based on the number of colors that are displayed on a graphics display.
Since a single screen comprising a graphics image may comprise millions of bits of video data, the video data must be compressed before being communicated between computers in a network. Compression enables the communication of video data in fewer bits (and in less time) than if the video data was communicated in its raw form. Typically, compression of video data involves compressing the pixel values that make up the frames of video data utilizing a compression algorithm. Many current compression algorithms are variants of the well known Lempel, Ziv, Welch (“LZW”) compression algorithm. The LZW algorithm automatically builds a dictionary of string patterns encountered in the data stream to be compressed. The dictionary does not need to be transmitted with the compressed data stream because the decompressor can build the dictionary in the same way that the compressor does.
Current video data compression algorithms based on the LZW process suffer from a number of drawbacks. One drawback results from the fact that the LZW algorithm utilizes only a single dictionary for storing previously encountered strings. Each string is represented in the dictionary by a word constructed from a code and a character. Therefore, assuming the code is X bits and the character is eight bits, then a given dictionary requires 2(X+8) address locations. For instance, a dictionary utilizing an 11 bit code requires 219 address locations (512K addresses). Because two bytes must be utilized to store each word, the size of the dictionary in this example is one megabyte (2*512K). Therefore, the dictionary size for a single dictionary capable of storing 2K items is one megabyte. The first 256 entries are reserved for single characters. The remaining entries can be utilized for storing compound words, which are words with two or more characters. As a result, a dictionary with 2K items can store 2K–256 compound words.
If the memory available in the computer system performing the decompression is exactly 512K, 1 MB, 2 MB, 4 MB, 8 MB, etc., then utilizing a single dictionary works well. However, in many cases additional memory may be available that is less than required to support codes having an additional bit. For instance, 3 MB may be available. This amount of memory is sufficient to support a dictionary having 4K codes (2 MB), but not a dictionary having 8K codes (4 MB). However, previous variants on the LZW algorithm are unable to effectively make use of the additional memory.
Another drawback to previous variants of the LZW algorithm is that compression and decompression can often be slow utilizing these algorithms. One reason for the poor performance is that a search must be made of the dictionary during each iteration to determine whether a matching string is in the dictionary. If a matching string is found, the code for the string is output. If a matching string is not found, then a new code is added to the dictionary for the current string. However, searching a large dictionary can be a time consuming process. Accordingly, it is desirable to reduce the number of times that the dictionary must be searched.
It is with respect to these considerations and others that the present invention has been made.